public class Percolation {
    private WeightedQuickUnionUF connectionGrid;
    private WeightedQuickUnionUF secretGrid;
    private boolean[][] grid;
    private int N;
    private boolean topOpen;

    public Percolation(int N) {
        connectionGrid = new WeightedQuickUnionUF((N + 2) * (N + 2));
        secretGrid = new WeightedQuickUnionUF((N + 2) * (N + 2));
        grid = new boolean[N + 2][N + 2];
        this.N = N;
        for (int i = 1; i <= N; i++) {
            connectionGrid.union(0, xyToID(1, i));
            secretGrid.union(xyToID(1, 1), xyToID(1, i));
            secretGrid.union(xyToID(N + 1, N + 1), xyToID(N, i));
        }

        grid[0][0] = true;
    }


    public void open(int i, int j) {
        if (i <= 0 || i > N)
            throw new IndexOutOfBoundsException("row index i out of bounds");
        if (j <= 0 || j > N)
            throw new IndexOutOfBoundsException("row index i out of bounds");
        grid[i][j] = true;
        if (i > 0 && j < N && isOpen(i, j + 1)) {
            connectionGrid.union(xyToID(i, j), xyToID(i, j + 1)); // right
            secretGrid.union(xyToID(i, j), xyToID(i, j + 1)); // right
        }
        if (j > 1 && i > 0 && isOpen(i, j - 1)) {
            connectionGrid.union(xyToID(i, j), xyToID(i, j - 1)); // left
            secretGrid.union(xyToID(i, j), xyToID(i, j - 1)); // left
        }
        if (i > 1 && j > 0 && isOpen(i - 1, j)) {
            connectionGrid.union(xyToID(i, j), xyToID(i - 1, j)); // top
            secretGrid.union(xyToID(i, j), xyToID(i - 1, j)); // top
        }
        if (j > 0 && i < N && isOpen(i + 1, j)) {
            connectionGrid.union(xyToID(i, j), xyToID(i + 1, j)); // bottom
            secretGrid.union(xyToID(i, j), xyToID(i + 1, j)); // bottom
        }
        //for percolation
        if (i == 1)
            topOpen = true;
    }

    public boolean isOpen(int i, int j) {
        if (i <= 0 || i > N)
            throw new IndexOutOfBoundsException("row index i out of bounds");
        if (j <= 0 || j > N)
            throw new IndexOutOfBoundsException("row index i out of bounds");
        return grid[i][j];
    }

    public boolean isFull(int i, int j) {
        if (i <= 0 || i > N)
            throw new IndexOutOfBoundsException("row index i out of bounds");
        if (j <= 0 || j > N)
            throw new IndexOutOfBoundsException("row index i out of bounds");
        return grid[i][j] && connectionGrid.connected(0, xyToID(i, j));
    }

    private int xyToID(int i, int j) {
        return (N + 2) * i + j;
    }

    public boolean percolates() {
        return topOpen && secretGrid.connected(xyToID(1, 1), xyToID(N + 1, N + 1));
    }
}